<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>寻路算法演示</title>
</head>
<style>
    html, body {

        width: 100%;

        height: 100%;

        font-family: monospace;

    }

    h1 {

        font-size: 50px;

        font-family: Lobster;

        position: relative;

        margin: 0 0 20px 0;

        padding: 0;

        font-weight: 400;

        text-align: center;

        color: #333;

        text-shadow: 1px 1px 3px #777;

    }


    #btns {

        text-align: center;

        margin-bottom: 30px;

    }


    .btn {

        border: 7px solid rgba(0, 0, 0, 0.2);

        border-radius: 5px;

        display: inline-block;

        padding: 5px 10px;

        cursor: pointer;

        color: #fff;

        position: relative;

        transition: all 0.2s ease;

        margin: 0 10px;

    }

    .btn.disabled {

        opacity: 0.5;

        pointer-events: none;

    }

    .btn:active {

        top: 1px;

    }


    #solve {

        background: #56bb56;

    }

    #solve:hover {

        background: #429142;

    }

    #solve:active {

        background: #7ADC7A;

    }


    #regen {

        background: #B52424;

    }

    #regen:hover {

        background: #8E1717;

    }

    #regen:active {

        background: #E63C3C;

    }


    #maze-holder {
        position: absolute;
        top: 0;
        left: 0;
        right: 0;
        bottom: 0;
        margin: 0 auto;
        width: 565px;
        display: table;

    }


    #maze {

        font-size: 0;

        width: 565px;

        height: 565px;

        border: 15px solid #ccc;

        border-radius: 15px;

        box-shadow: 0 0 0 1000000px #f0f0f0;

        z-index: -1;

    }


    .cell {

        color: #333;

        height: 23px;

        width: 23px;
        display: inline-block;

        box-sizing: border-box;

        margin: 0 -7px -7px 0;

        position: relative;
    }

    .cell[data-north=true] {
        border-top: 7px solid;
    }

    .cell[data-south=true] {
        border-bottom: 7px solid;
    }

    .cell[data-east=true] {
        border-right: 7px solid;
    }

    .cell[data-west=true] {
        border-left: 7px solid;
    }

    .cell[data-solution=true]:not([data-start=true]):not([data-end=true]):before {

        background: #E2E215;

        content: "a";

        position: absolute;

        top: 0px;

        left: 0px;

        right: 0px;

        bottom: 0px;

        z-index: -1;

    }

    .cell[data-start=true] {

        background: #56bb56;

        z-index: 1;

    }

    .cell[data-end=true] {

        background: #B52424;

        z-index: 1;

    }

</style>
<body>

<div id="maze-holder">
    <h1>迷宫（BFS寻路）</h1>
    <div id="btns">
        <select id="sel" style="border: 7px solid rgba(0, 0, 0, 0.2);
            border-radius: 5px;
            display: inline-block;
            padding: 5px 10px;
            cursor: pointer;
            position: relative;
            transition: all 0.2s ease;
            margin: 0 10px;">
            <option value="BFS">BFS</option>
            <option value="A*" selected="selected">A*</option>
        </select>
        <div class="btn" id="solve">solve</div>
        <div class="btn" id="regen">regenerate</div>
        <p id="desc">
    </div>
    <div id="maze"></div>
</div>
<script src="https://www.jq22.com/jquery/1.11.1/jquery.min.js"></script>
<script>
    var html = $("#maze")

    function Cell(I, J) {
        this.i = I;
        this.j = J;
        this.visited = false;
        this.start = false;
        this.end = false;
        this.path = false;
        this.correct_path = false;
        this.walls = {
            n: true,
            s: true,
            e: true,
            w: true
        }
        this.print = function () {
            // return '<div id="cell_' + this.i +'_'+ this.j + '" data-solution="' + this.correct_path + '" data-west="' + this.walls.w + '" data-east="' + this.walls.e + '" data-north="' + this.walls.n + '" data-south="' + this.walls.s + '" class="cell" data-start="' + this.start + '" data-end="' + this.end + '" data-visited="' + this.visited + '"></div>'

            return '<div id="cell_' + this.i + '_' + this.j + '" data-solution="' + this.correct_path
                + '" data-west="' + this.walls.w
                + '" data-east="' + this.walls.e
                + '" data-north="' + this.walls.n
                + '" data-south="' + this.walls.s
                + '" class="cell" data-start="' + this.start
                + '" data-end="' + this.end
                + '" data-visited="' + this.visited + '"></div>'
        }
    }

    var maze = {
        height: 35,
        width: 35,
        openList: [],
        visited_cells: []
    }

    maze.init = function () {
        maze.cells = [[]]
        for (var i = 0; i < this.width; i++) {
            maze.cells[i] = [];
            for (var j = 0; j < this.height; j++) {
                maze.cells[i][j] = new Cell(i, j);
            }
        }
        maze.cells[0][0].start = true;
        maze.cells[this.width - 1][this.height - 1].end = true;
        // maze.cells[this.width - 1][this.height - 1].walls.e = false;
        // maze.cells[0][0].walls.w = false;
        // maze.cells[0][0].walls.w = false;
    }

    maze.print = function () {
        var new_html = ''
        for (var i = 0; i < this.width; i++) {
            for (var j = 0; j < this.height; j++) {
                new_html += this.cells[i][j].print();
            }
            new_html += '<br style="clear:both" /> '
        }
        html.html(new_html)
    }

    maze.print_solution = function () {
        setTimeout(function () {
            var cell = maze.solution_copy.pop()
            document.getElementById('cell_' + cell.i + '_' + cell.j).setAttribute('data-solution', "true")
            if (maze.solution_copy.length != 0) {
                maze.print_solution()
            } else {
                $("#solve").text("solved").addClass('disabled')
                $("#regen").removeClass("disabled")
            }
        }, 50)
    }

    function randomUniqueNumber(len) {
        return Math.ceil(Math.random() * (len)) - 1;
    }

    maze.mazifiy = function (i, j) {
        maze.visited_cells.push(maze.cells[i][j])
        maze.cells[i][j].visited = true;
        var invalid = true;
        var counter = 0;

        while (invalid && counter < 4) {
            invalid = false;
            counter++;
            var randomSide = randomUniqueNumber(4);
            if (randomSide == 0 && i > 0 && !maze.cells[i - 1][j].visited) {
                maze.cells[i][j].walls.n = false;
                maze.cells[i - 1][j].walls.s = false;
                maze.mazifiy(i - 1, j)
            } else if (randomSide == 1 && i < maze.height - 1 && !maze.cells[i + 1][j].visited) {
                maze.cells[i][j].walls.s = false;
                maze.cells[i + 1][j].walls.n = false;
                maze.mazifiy(i + 1, j)
            } else if (randomSide == 2 && j < maze.width - 1 && !maze.cells[i][j + 1].visited) {
                maze.cells[i][j].walls.e = false;
                maze.cells[i][j + 1].walls.w = false;
                maze.mazifiy(i, j + 1)
            } else if (randomSide == 3 && j > 0 && !maze.cells[i][j - 1].visited) {
                maze.cells[i][j].walls.w = false;
                maze.cells[i][j - 1].walls.e = false;
                maze.mazifiy(i, j - 1)
            } else {
                invalid = true;
            }
        }

        maze.visited_cells.pop()
        var last = maze.visited_cells.pop();
        if (last != undefined) {
            maze.mazifiy(last.i, last.j)
        }
    }

    maze.solve = function (i, j) {
        var cell = maze.cells[i][j];
        if (cell.end) return true;
        if (cell.path) return false;
        cell.path = true;
        //BFS
        if (i > 0 && !cell.walls.n && maze.solve(i - 1, j)) {
            maze.solution.push(cell)
            return true
        }
        if (i < maze.height - 1 && !cell.walls.s && maze.solve(i + 1, j)) {
            maze.solution.push(cell)
            return true
        }
        if (j > 0 && !cell.walls.w && maze.solve(i, j - 1)) {
            maze.solution.push(cell)
            return true
        }
        if (j < maze.width - 1 && !cell.walls.e && maze.solve(i, j + 1)) {
            maze.solution.push(cell)
            return true
        }
        return false;
    }

    maze.aStarSolve = function () {
        while (maze.openList.length > 0) {
            var cell = maze.openList.pop();
            if (cell.end) return true;
            if (cell.path) continue;

            var i = cell.i;
            var j = cell.j;

            neighbors = [];
            if (i > 0 && !cell.walls.n) {
                neighbors.push(maze.cells[i - 1][j])
            }
            if (i < maze.height - 1 && !cell.walls.s) {
                neighbors.push(maze.cells[i + 1][j])
            }
            if (j > 0 && !cell.walls.w) {
                neighbors.push(maze.cells[i][j - 1])
            }
            if (j < maze.width - 1 && !cell.walls.e) {
                neighbors.push(maze.cells[i][j + 1])
            }
            cell.visited = false;
            var neis = []
            for (var p = 0; p < neighbors.length; p++) {
                var nei = neighbors[p];
                var h = this.manhattan(cell, nei)
                var g = this.manhattan(cell, maze.cells[this.width - 1][this.height - 1])
                var f = h + g;
                var t = {}
                t.f = f, t.nei = nei;
                neis.push(t);
            }
            if (neis.length > 0) {
                var f0 = neis[0].f;
                for (var m = 0; m < neis.length; m++) {
                    nei = neis[m]
                    if (nei.f < f0) {
                        f0 = nei.f
                        maze.openList.push(nei.nei)
                    }
                    if (nei.f = f0) {
                        f0 = nei.f
                        maze.openList.push(nei.nei)
                    }
                }

                cell.path = true;
                maze.solution.push(cell)
            }

        }
    }

    maze.manhattan = function (cur, tar) {
        var i1 = cur.i;
        var j1 = cur.j
        var i2 = tar.i
        var j2 = tar.j
        return Math.abs(i1 - i2) + Math.abs(j1 - j2);
    }

    maze.openList = [];
    maze.visited_cells = [];
    maze.solution = []
    maze.init()
    maze.mazifiy(0, 0)
    maze.print()

    $("#regen").click(function () {
        $("#solve").text("solve").removeClass("disabled")
        $(this).addClass('disabled')
        maze.visited_cells = []
        maze.solution = []
        maze.init()
        maze.mazifiy(0, 0)
        maze.print()
        $(this).removeClass('disabled')
    })

    $("#solve").click(function () {
        $(this).text("solving..").addClass("disabled")
        $("#regen").addClass("disabled")
        maze.solution = [];
        var sel = $("#sel").val();
        if (sel === "BFS") {
            var start = performance.now();
            maze.solve(0, 0);
            var end = performance.now();
            console.log('BSF cost is', `${end - start}ms`)
        } else if (sel == "A*") {
            var start = performance.now();
            maze.openList.push(maze.cells[0][0]);
            maze.aStarSolve()
            maze.solution_copy = maze.solution.reverse();
            var end = performance.now();
            console.log('A* cost is', `${end - start}ms`)
        }
        maze.solution_copy = maze.solution.concat([]);
        maze.print_solution()
    })

</script>
</body>
</html>
